The present invention relates to digital data transmission and, more particularly, to interface equipment between a digital data bus and user equipment.
A distributed digital data system consists of a plurality of locations capable of communicating with each other over a suitable communications system. Each location, called a node, may receive, transmit, or both. A node may be, for example, a stand-alone personal computer with autonomous computing capability, a dumb terminal without autonomous computing capability, a printer, a communications link, or a gateway to a different network.
Three general classes of networks are in common use:
star,
ring,
bus.
In a star network, each node is directly connected by a dedicated cable radiating outward from a network server. Such a network requires large amounts of cabling to make the required interconnections. In addition, the network server is typically at least a smart terminal whose total performance is sacrificed to the needs of the network. Since a star network provides dedicated links for each node, the problem of interference between nodes attempting simultaneous access to a shared communication asset does not arise.
A ring network, as its name implies, connects adjacent nodes into a closed ring. A message originating in one node is passed on interconnecting cable to its adjacent node. If the message is addressed to the adjacent node, the adjacent node detects this fact and acts to receive it. If the message is not addressed to the adjacent node, it is passed on to the next node in the ring until the addressee node is found. Upon reception, the receiving node may place an acknowledgement message on the cable addressed to the node originating the message to confirm receipt. The acknowledgement message progresses from node to node until it is received at the original destination. The unidirectional data flow in a ring network tends to limit the data rate. In addition, since each node is responsible for passing unaccepted messages to its neighbor, failure of one node can interrupt the entire network.
A bus is a linear network consisting of a twisted-pair or coaxial link to which nodes are attached at convenient locations. All nodes apply messages to the bus and monitor the bus for messages addressed to them. Failure of one node normally cannot halt network operation. The linear nature of the bus avoids the cabling costs of the star network. Most common busses carry serial data at data rates varying from a few kilobits per second to hundreds of megabits per second.
A bus network, to which the present invention is addressed, must provide means for directing data between any two specific nodes and for dealing with the problem of two or more nodes demanding access to the bus at the same time. For present purposes, the following description is directed to an embodiment of the invention for use with a bus protocol described in the IEEE Network Standard 802.3. One commercial network system embodying the 802.3 standard is known as Ethernet and is available from 3 Com. The IEEE Network Standard 802.3 specifies a baseband system having a bit rate of 10 megabits per second. As will be later detailed, the actual ability of such a bus network to communicate intelligence is considerably lower than its bit rate.
One skilled in the art will recognize that the present invention is not limited to a particular bit rate or to a baseband system communicating on wires or coaxial cables. It is within the contemplation of the present invention to employ the techniques disclosed herein in a broadband system which may be communicated between nodes on media other than wires or coaxial cables. Broadband systems may employ a plurality of subcarriers upon each of which is imposed one data channel. Each such data channel may be considered the equivalent of an 802.3 baseband channel. Transmission media may include, for example, microwave transmission for covering at least part of the distance between nodes. Optical transmission is equally a candidate. Optical transmission may take place in air or may be constrained to optical communications media such as, for example, glass fibers. Glass fibers offer greater bandwidths which may be on the order of gigabits per second.
Bus transmission employs data packets which may be of fixed or variable length. A data packet contains a header, data and a trailer. The data in a data packet may be only part of a total message from the transmitting to the destination node. The header provides synchronizing signals, identifies the source and intended destination of the data, and includes information identifying the sequence that data in the data packet occupies with respect to data in related data packets. The trailer typically contains a cyclic-redundancy-check, or checksum, message the receiving node uses to verify that the data is received without error.
According to the Ethernet standard, a data packet has a fixed maximum length regardless of the length of the total message being transmitted. The header and trailer contain no intelligence and are therefore considered overhead to the data transmission. The ratio of overhead to data depends on the size of the header and trailer and the length of the data portion contained therein. Some systems require the ability to deal with short messages. Such systems may employ data packets having a total length of, for example, 128 bytes (eight-bit words) with a header of 44 bytes and a trailer of four bytes thus leaving 80 bytes for data. The efficiency degrades even further if the tyical message consists of less than 80 bytes. Although a relatively inefficient data transmission technique, it is optimized for short data transmission.
For longer messages, longer data packets improve the transmission efficiency. The above Ethernet system, for example, employs data packets of about 1500 bytes with a 44-byte overhead. The overhead thus becomes a relatively small percentage of the data packet.
One application of bus transmission we foresee for the present invention includes transmission of graphic data. Such graphic data typically comprises several hundred thousand to several million bytes per message. A larger data packet is therefore indicated for achieving high transmission efficiency. In a graphics data transmission system, a data packet length of about 4,000 bytes may be employed. When the data portion of the data packet is filled, the ratio of overhead to total length becomes insignificant. In the usual case, the last data packet is only partly filled. The unfilled part of the last data packet in a message is overhead. A system transmitting graphics data with a bus speed of, for example, 9.6 megabits per second may achieve a data-transmission rate on the order of about 9 megabits per second.
The equipment using bus data may be send/receive, receive-only, or send-only. A send/receive equipment may be a computer terminal. A receive-only equipment may be a graphics display or a printer. A send-only equipment may be a video camera chain, a CAT (computer axial tomography) scanner, or a magnetic resonance scanner.
Each node requires interface equipment for interfacing the user equipment with the bus data. The transmitting node performs calculations to break a long message into data packets, appends header and trailer and accesses the bus. The receiving node monitors the bus until its unique identifier is detected, accepts the data packet, calculates a cyclic redundancy check (CRC) or checksum for the data packet as well as a large number of other tests on the data packet and transmits an acknowledgement on the bus addressed to the transmitting node when requested to do so. When the calculated and received CRCs or checksums and other tests fail to agree, the receiving node scraps the data in the data packet and, in response to an acknowledgement request, places a message on the bus addressed to the transmitting node informing it of such failure. The transmitting node thereupon makes further attempts to transmit the data packet until agreement is found at the receiving node.
As noted above, all nodes have independent abilities to access the bus at any time. If two nodes transmit at the same time, data in both data packets is garbled. In a system with many nodes, a small probability exists that two nodes attempt to access the bus at the same time. The 802.3 standard avoids garble and data loss using a carrier-sense, multiple-access system with collision detection (CSMA/CD). Before transmitting, a node listens to the bus. If it detects data being transmitted on the bus, it waits until the bus is free and then begins to send. If two nodes begin transmitting at the same time, a collision results. Both transmitting nodes monitor the bus during their transmissions to detect a condition indicating the presence of more than one signal. If more than one signal is detected, both stop transmitting and remain silent for a timeout period whose length is randomly determined. The interface equipments determine the disposition of any partial data transmission up to the time of collision detection.
In some cases, the partial data transmissions are scrapped. The randomness of the timeout period guarantees that one of the nodes reaches the end of its timeout period before the other node. The earlier node listens on the bus, detects no data transmission, and begins retransmitting its prior data packet. The later node listens on the bus, detects the data transmission of the earlier node, and stands by until it detects a clear bus before beginning transmission. The time wasted during partial data transmission and the mandatory delay for both nodes reduces the effective transmission rate of the bus. When a large number of nodes are present on the bus, such reduction may become a significant fraction of the theoretical bus transmission rate.
Overhead tasks such as the assembly of data packets, testing of received data packets, and dealing with collision avoidance, place significant burdens on the interface equipment. The interface equipment conventionally performs the overhead and transmission or reception serially. That is, while transmission or reception of a data packet occurs, nothing else is done by the interface equipment. The overhead tasks may be interleaved with transmission and reception but they share memory and processor time. As a consequence, gaps occur in the transmission and reception of data to accommodate the overhead activities. We have observed that the effective transmission rate of a bus system capable of a burst transmission rate of 10 megabits per second rate may fall to less than 2 megabits per second when overhead tasks are taken into account.